#include "InterferenceAnalysis.h"

namespace Compiler
{
	namespace Intermediate
	{
		List<RefPtr<LiveRange>> InterferenceAnalysis::ComputeLiveRanges(ControlFlowGraph * program, int & ranges)
		{
			List<RefPtr<LiveRange>> rs;
			rs.Reserve(program->Variables.Count());
			int id = 0;
			for (auto & var : program->Variables)
			{
				auto range = new LiveRange();
				if (var->Id != id)
					throw InvalidProgramException(L"Inconsistent variable ids");
				range->Id = id++;
				range->VarSet.SetMax(program->Variables.Count());
				range->VarSet.Add(var->Id);
				rs.Add(range);
			}
			for (auto & node : program->Nodes)
			{
				for (auto & instr:node->Code)
				{
					if (instr.Func == Operation::Phi)
					{
						RefPtr<LiveRange> range = rs[instr.LeftOperand.Var->Id];
						for (auto & op : instr.Operands)
						{
							auto & curRange = rs[op.Var->Id];
							range->VarSet.UnionWith(curRange->VarSet);
							curRange = range;
						}
					}
				}
			}
			HashSet<int> idDedupe;
			List<LiveRange *> dRanges;
			dRanges.Reserve(rs.Count());
			for (auto & range : rs)
			{
				if (idDedupe.Add(range->Id))
				{
					dRanges.Add(range.Ptr());
				}
			}
			for (int i = 0; i<dRanges.Count(); i++)
				dRanges[i]->Id = i;
			ranges = idDedupe.Count();
			return rs;
		}

		InterferenceGraph InterferenceAnalysis::BuildInterferenceGraph(ControlFlowGraph * program)
		{
			InterferenceGraph rs(program->Variables.Count());
			program->ComputeVariableLiveness();
			EnumerableIntSet liveNow;
			liveNow.SetMax(program->Variables.Count());
#ifdef _DEBUG
			// check variable id integrity
			for (int i = 0; i<program->Variables.Count(); i++)
				if (i != program->Variables[i]->Id)
					throw InvalidProgramException(L"Variable Id integrity check failed.");
#endif
			IntSet excludeSet;
			excludeSet.SetMax(program->Variables.Count());
			for (auto & node : program->Nodes)
			{
				// build live now
				liveNow.Clear();
				liveNow.UnionWith(node->LiveOut);
				for (auto iter = node->Code.LastNode(); iter; iter = iter->GetPrevious())
				{
					auto & instr = iter->Value;
					
					if (instr.LeftOperand.IsVariable())
					{
						int var0 = instr.LeftOperand.Var->Id;
						int varExclude = -1;
						if (instr.Func == 0 && instr.Operands[0].IsVariable())
						{
							for (auto var : liveNow.Values)
								if (var != instr.Operands[0].Var->Id)
									rs.AddEdge(var0, var);
						}
						else if (instr.Func == Operation::Phi)
						{
							excludeSet.Clear();
							for (auto op : instr.Operands)
								excludeSet.Add(op.Var->Id);
							for (auto var : liveNow.Values)
								if (!excludeSet.Contains(var))
									rs.AddEdge(var0, var);
						}
						else
						{
							for (auto var : liveNow.Values)
								rs.AddEdge(var0, var);
						}
						// update liveNow
						liveNow.Remove(var0);
					}
					for (auto & op : instr.Operands)
						if (op.IsVariable())
							liveNow.Add(op.Var->Id);
				}
			}
			return rs;
		}
	}
}